package oj;

//链表的回文结构：对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构，给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
//思路：将链表从中间开始逆置，得到两个链表c1,c2，比较两个链表是否完全相同，如果完全相同那么原链表就是回文链表
public class Solution_OR36 {
    //求链表的元素个数
    private static int sizeOf(ListNode head){
        int size = 0;
        for(ListNode cur = head;cur != null;cur = cur.next){
            size++;
        }
        return size;
    }
    //求链表的中间结点
    private static ListNode middleOf(ListNode head){
        int size = sizeOf(head);
        ListNode ans = head;
        int x = size / 2;
        for (int i = 0; i < x; i++) {
            ans = ans.next;
        }
        return ans;
    }
    //逆置链表
    private static ListNode reverseList(ListNode head){
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
    public boolean chkPalindrome(ListNode A) {
        //找中间结点
        ListNode midNode = middleOf(A);
        //逆置
        ListNode rHead = reverseList(midNode);
        //两个链表
        ListNode c1 = A;
        ListNode c2 = rHead;
        //进行比较
        while (c1 != null && c2 != null){
            if(c1.val != c2.val){
                return false;
            }
            c1 = c1.next;
            c2 = c2.next;
        }
        return true;
    }
}
